// https://leetcode.cn/problems/wildcard-matching/description/

// 算法思路总结：
// 1. 动态规划解决通配符匹配问题
// 2. dp[i][j]表示s的前i个字符与p的前j个字符是否匹配
// 3. 字母匹配：s[i]==p[j]且dp[i-1][j-1]为真
// 4. '?'匹配：匹配任意单个字符，dp[i-1][j-1]为真
// 5. '*'匹配：匹配零个(dp[i][j-1])或多个字符(dp[i-1][j])
// 6. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <algorithm>

class Solution 
{
public:
    bool isMatch(string s, string p) 
    {
        s = " " + s;
        p = " " + p;
        int m = s.size(), n = p.size();

        vector<vector<bool>> dp(m, vector<bool>(n, false));
        dp[0][0] = true;

        for (int j = 1 ; j < n ; j++)
        {
            if (p[j] == '*')
                dp[0][j] = true;
            else break;
        }

        for (int i = 1 ; i < m ; i++)
        {
            for (int j = 1 ; j < n ; j++)
            {
                if (isalpha(p[j]) && s[i] == p[j])
                    dp[i][j] = dp[i - 1][j - 1];
                else if (p[j] == '?')
                    dp[i][j] = dp[i - 1][j - 1];
                else if (p[j] == '*')
                {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }

        return dp[m - 1][n - 1];
    }
};

int main()
{
    string s1 = "aa", p1 = "a";
    string s2 = "aa", p2 = "*";

    Solution sol;

    cout << (sol.isMatch(s1, p1) == 1 ? "true" : "false") << endl;
    cout << (sol.isMatch(s2, p2) == 1 ? "true" : "false") << endl;

    return 0;
}